package leetcode_301_400;

import java.awt.*;
import java.util.*;

public class LeeCode_313 {
    public static void main(String[] args) {
        System.out.println(nthSuperUglyNumber(12, new int[]{2, 7, 13, 19}));
        System.out.println(nthSuperUglyNumber(1, new int[]{2,3,5}));
        System.out.println(nthSuperUglyNumber(15, new int[]{3,5,7,11,19,23,29,41,43,47}));
        System.out.println(nthSuperUglyNumber2(10, new int[]{3,5,7}));
    }
    private static int nthSuperUglyNumber(int n, int[] primes) {
        long[] dp = new long[n + 1];
        long m = primes.length;
        long[] po = new long[(int) m];
        long[] nums = new long[(int) m];
        Arrays.fill(nums, 1);
        for (int i = 1; i <= n; i++) {
            long min = Arrays.stream(nums).min().getAsLong();
            dp[i] = min;
            for (int j = 0; j < m; j++) {
                if (nums[j] == min) {
                    po[j]++;
                    nums[j] = (int) (dp[(int) po[j]] * primes[j]);
                }
            }
        }
        return (int) dp[n];
    }
    private static int nthSuperUglyNumber2(int n, int[] primes) {
        TreeSet<Long> set = new TreeSet<>();
        long res = 1;
        for (int i = 1; i < n; i++) {
            for (int prime : primes) {
                set.add(res * prime);
            }
            res = set.pollFirst();
            while (!set.isEmpty() && set.first() <= res){
                set.pollFirst();
            }
        }
        return (int) res;
    }
}
